/**
 * 1217. 玩筹码
 * https://leetcode-cn.com/problems/minimum-cost-to-move-chips-to-the-same-position/
 */
public class Solutions_1217 {
    public static void main(String[] args) {
        int[] position = {1, 2, 3};  // output: 1
//        int[] position = {2, 2, 2, 3, 3};  // output: 2
//        int[] position = {1, 2, 2, 2, 2};  // output: 1

        int result = minCostToMoveChips(position);
        System.out.println(result);
    }

    /**
     * int[] position = {2, 2, 2, 3, 3};  // output: 2
     * position[0] = 2, 表示有一个筹码在索引 2 上
     * position[1] = 2, 表示有一个筹码在索引 2 上
     * position[2] = 2, 表示有一个筹码在索引 2 上
     * position[3] = 3, 表示有一个筹码在索引 3 上
     * position[4] = 3, 表示有一个筹码在索引 3 上
     * 最终索引 2 上的筹码数量为 3，索引 3 上的筹码数量为 2（经“移动”后，全部的筹码都可以集中到一个奇数索引上，一个偶数索引上，且代价为 0）
     * 那么不论是将索引 2 上的 3 个筹码移动到索引 3 上，还是将索引 3 上的筹码移动到索引 2 上，都可以将 position 中的筹码，全部在一个索引上
     * 那么要想代价最小，就只有将筹码数量小的一方，移动到筹码数量较多的一方
     */
    public static int minCostToMoveChips(int[] position) {
        // 记录偶数索引上筹码的个数
        int even = 0;
        // 记录奇数索引上筹码的个数
        int odd = 0;
        for (int num : position) {
            if (num % 2 == 0) {
                even ++;
            } else {
                odd ++;
            }
        }
        // 奇数索引上的元素全部移动到偶数索引上？还是偶数索引上的元素全部移动到奇数索引上？
        // 索引上的筹码越少，那么代价就越小
        return Math.min(odd, even);
    }
}
